package 栈;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 中缀表达式转后缀表达式思路：
 * 分类讨论
 * 初始化：创建一个数字栈和和一个运算符栈
 * 依次扫描中缀表达式
 * 1，碰到数字
 * 直接压入数字栈
 * 2，遇到运算符时
 * a，如果运算符栈为空，或者栈顶为左括号"("，直接入栈
 * b，如果当前运算符优先级比栈顶运算符高，也之间入栈
 * c，否则，将运算符栈栈顶元素压入到数字栈中，再次转到a进行比较
 * 3，碰到括号时
 * a，如果是左括号"("，直接入栈
 * b，如果是右括号")"，则依次弹出运算符栈栈顶的元素，压入数字栈，遇到左括号"("为止
 * ，将这一对括号丢弃
 * <p>
 * 结果：遍历到结尾，将运算符栈中剩下的元素依次弹出压入数字栈，将数字栈依次弹出，反转之后即为后缀表达式（逆波兰表达式）
 */
public class 中缀表达式转后缀表达式 {

    public static void main(String[] args) {

        String infix = "1+((24+3)*4)-5";
        System.out.println(infix2Suffix(infix));

    }

    public static List<String> infix2Suffix(String infix) {
        List<String> suffixList = new ArrayList<>();
        Deque<String> numQueue = new ArrayDeque<>();  // 直接用队列最后无需反转
        Deque<Character> operateStack = new ArrayDeque<>();

        int cur = 0;
        while (cur < infix.length()) {
            char curChar = infix.charAt(cur);
            if (Character.isDigit(curChar)) {  // 需要考虑多位数
                int right = cur + 1;
                while (right < infix.length() && Character.isDigit(infix.charAt(right))) {
                    right++;
                }
                numQueue.addLast(infix.substring(cur, right));
                cur = right;
                continue;
            } else if (curChar == '(') {
                operateStack.addFirst(curChar);
            } else if (curChar == ')') {
                // 依次弹出运算符栈栈顶的元素，压入数字栈，遇到左括号"("为止
                while (!operateStack.isEmpty() && operateStack.peek() != '(') {
                    numQueue.addLast(operateStack.pollFirst().toString());
                }
                operateStack.pollFirst();  // 去除掉左括号
            } else {
                while (true) {
                    if (operateStack.isEmpty() || operateStack.peek() == '(') {
                        operateStack.addFirst(curChar);
                        break;
                    } else if (isBigOperate(curChar, operateStack.peek())) {
                        operateStack.addFirst(curChar);
                        break;
                    } else {
                        numQueue.addLast(operateStack.pollFirst().toString());
                    }
                }
            }
            cur++;
        }
        // 将运算符栈中剩下元素全部压入数字栈中
        while (!operateStack.isEmpty()) {
            numQueue.addLast(operateStack.pollFirst().toString());
        }
        while (!numQueue.isEmpty()) {
            suffixList.add(numQueue.pollFirst());
        }
        return suffixList;
    }

    public static boolean isBigOperate(char cur, char peek) {
        if (cur == '*' || cur == '/' && peek == '+' || peek == '-') {
            return true;
        }
        return false;
    }

}
